#ifndef __BVH__
#define __BVH__

#ifndef L_VERSION
#define L_VERSION   1111225
#endif

#include <llib.h>
using namespace llib;
using namespace llib::geom;

#include <vector>
#include <deque>
using namespace std;

class BV_AABB {
public:
    enum ConstructionMode { CenterRadiusConstruction, MaxMinConstruction };

    BV_AABB() {}
    BV_AABB(const Vec3f& centerOrMax, const Vec3f& radiusOrMin, 
        const ConstructionMode mode = CenterRadiusConstruction);

    void Update(const Vec3f& centerOrMax, const Vec3f& radiusOrMin, const ConstructionMode mode = CenterRadiusConstruction);

    inline const Vec3f GetMax() const       { return _center + _radius; }
    inline const Vec3f GetMin() const       { return _center - _radius; }
    inline const Vec3f GetCenter() const    { return _center; }
    inline const Vec3f GetRadius() const    { return _radius; }

private:
    Vec3f _center;
    Vec3f _radius;

};

class BVNode {
public:
    BVNode() {}

    Boolean         BVIntersection(const BVNode* another) const;
    static Boolean  CheckBVIntersection(const BVNode* left, const BVNode* right);

    void            UpdateBV(const Vec3f& centerOrMax, const Vec3f& radiusOrMin,
                        const BV_AABB::ConstructionMode mode = BV_AABB::CenterRadiusConstruction);

    inline const BV_AABB& GetBV() const { return _bv; }

private:
    BV_AABB         _bv;

};

class BVTree {
public:
    /* Constructor */
    BVTree() : _nodeList(NULL), _leafElemIndexList(NULL), _firstLeafIndex(-1), _lastLeafIndex(-1), _nodeNum(0), _leafNum(0) {}
    /* Destructor
       The destructor need to free all tree nodes.
     */
    ~BVTree();

    /* Copy */
    BVTree(const BVTree& tree);

    /* Assignment operator */
    BVTree& operator=(const BVTree& tree);

    /* Building hierarchy according to elements' center position */
    void Build(const vector<Vec3f>& elementPostions);

    /* The hierarchy node number */
    inline Int32 GetNodeNum() const { return _nodeNum; }
    inline Int32 GetLeafNum() const { return _leafNum; }

    /* Fetch the root node pointer */
    inline BVNode* GetRoot() const { return _nodeList; }

    /* child node traversal */
    BVNode* GetLeftChild(const BVNode* node) const;
    BVNode* GetRightChild(const BVNode* node) const;

    /* Node property query */
    Boolean IsLeafNode(const BVNode* node) const;
    Int32   GetLeafElemIndex(const BVNode* node) const;

    /* Here we define the traversal type for the generic traversal method */
    enum TraversalType { Preorder = 0, Inorder = 1, Postorder = 2, Hierarchy = 3, LeafOnly = 4 };

    /* The step-by-step traversal */
    void    TraversalBegin(TraversalType type);
    BVNode* TraversalNext();
    void    TraversalEnd() { _traversalHelper.clear(); _traversalNextFunPtr = NULL; }

    /* The integrated traversal */
    void    Traversal( TraversalType type, Boolean (*callback)(const BVTree& tree, BVNode* curNode) );
    template <class Functor_t>
    void    Traversal( TraversalType type, Functor_t& functor );

private:
    BVNode* _nodeList;
    Int32*  _leafElemIndexList;

    Int32   _firstLeafIndex;
    Int32   _lastLeafIndex;

    Int32   _nodeNum;
    Int32   _leafNum;

    deque<Int32> _traversalHelper;
    Int32   _lastPop;
    BVNode* (BVTree::*_traversalNextFunPtr)(void);

    /* copy constructor & operator = */
    void    copy(const BVTree& tree);

    /* build */
    void    leafArrangement(const vector<Vec3f>& elementPostions, vector<Int32>& leafIndex) const;
    Int32   completeBinaryTreeLeafDivide(Int32 leafNum) const;

    /* index query */
    inline Int32 getNodeIndex(const BVNode* node) const {
        Int32 index = (Int32)(node - _nodeList);
        return (index >= 0 && index < _nodeNum) ? index : -1;
    }
    inline Int32 getLeafIndex(const BVNode* leaf) const {
        Int32 index = getNodeIndex(leaf);
        index -= _nodeNum - _leafNum;
        return (index >= 0 && index < _leafNum) ? index : -1;
    }

    /* The traversal stuff */
        /* Preorder */
    void    traversalBegin_Preorder() { _traversalHelper.push_back(0); _traversalNextFunPtr = &BVTree::traversalNext_Preorder; }
    BVNode* traversalNext_Preorder();
        /* Inorder */
    void    traversalBegin_Inorder() { Int32 id = 0; while(id < _nodeNum) { _traversalHelper.push_back(id); id = id * 2 + 1; } _traversalNextFunPtr = &BVTree::traversalNext_Inorder; }
    BVNode* traversalNext_Inorder();
        /* Postorder */
    void    traversalBegin_Postorder() { _lastPop = -1; Int32 id = 0; while(id < _nodeNum) { _traversalHelper.push_back(id); id = id * 2 + 1; } _traversalNextFunPtr = &BVTree::traversalNext_Postorder; }
    BVNode* traversalNext_Postorder();
        /* Hierarchy */
    // ...
        /* LeafOnly */
    // ...





    Int32   getPrevLeafIndex(const Int32 nodeId) const;
    Int32   getNextLeafIndex(const Int32 nodeId) const;


};














#endif
